Homomorphic secret sharing

In cryptography, homomorphic secret sharing is a type of secret sharing algorithm in which the secret is encrypted via homomorphic encryption. A homomorphism is a transformation from one type of algebraic structure into another so that the structure is preserved. Importantly, this means that for every kind of manipulation of the original data, there is a corresponding manipulation of the transformed data.[1]

Contents

[hide]

Technique

Homomorphic secret sharing is used to transmit a secret to several recipients as follows:

  1. Transform the "secret" using a homomorphism. This often puts the secret into a form which is easy to manipulate or store. In particular, there may be a natural way to 'split' the new form as required by step (2).
  2. Split the transformed secret into several parts, one for each recipient. The secret must be split in such a way that it can only be recovered when all or most of the parts are combined. (See secret sharing)
  3. Distribute the parts of the secret to each of the recipients.
  4. Combine each of the recipients parts to recover the transformed secret, perhaps at a specified time.
  5. Reverse the homomorphism to recover the original secret.

Example: decentralized voting protocol

Shamir's secret sharing is a kind of homomorphic secret sharing in which a secret, represented by a number, is transformed into a polynomial. As a specific application, suppose a community is worried about corrupt authorities tampering with their votes. Instead of sending their votes to a single authority who might be corrupt, they decide to use secret sharing to distribute encrypted fragments of their votes to several authorities, hoping to decentralize the vote-counting process. In fact, Shamir's secret sharing has several advantages, which are discussed in more detail below. The protocol proceeds as follows:

Suppose that we have a simple ballot where a voter can either choose to vote yes (represented by the number +1) or no (represented by the number -1), and suppose there are k authorities who will be receiving the parts of votes.

  1. Each voter generates a random polynomial of degree k-1. P(x) = a_{k-1}x^{k-1}%2B\ldots%2Ba_1x^1%2Ba_0. The constant term a_0 will equal the option they voted for, i.e. a_0 will be either +1 or -1.
  2. Each authority has a publicly-known ID number t_k. Next, the voter calculates P(t_k) for each of the k authorities. The P(t_k) are the pieces of the secret, which are distributed to the corresponding k recipients along with their voter ID.
    • The secret is secure because it takes k points to recover a polynomial of degree k-1. (Two points determine a line, three points determine a parabola, and so on)
    • Since it is mathematically impossible to determine the voter's choice with only one piece of the secret, the voter ID doesn't have to be confidential.
    • Additionally, this system resists tampering because no authority would be able to predict how altering their piece would affect the vote.
  3. After voting has been completed, each authority adds up the pieces he has received from all of the voters, and then sends this sum to the rest of the authorities.
    • Recall that the secret has been transformed via  f: \text{vote} \rightarrow \text{polynomial}. Because f was a homomorphism, adding up the polynomials precisely corresponds to adding up the votes, that is f^{-1}(\text{sum of polynomials})=\text{sum of votes}.
  4. When the k sums from the k authorities are all known, the sum-polynomial Q(x)=A_{k-1}x^{k-1}%2BA_{k-2}x^{k-2}%2B\ldots%2BA_1x^1%2BA_0 can be calculated. A_0 will be the sum of all the votes received. (Hence if A_0 is positive, more votes were received for yes than no, and if A_0 is negative, more votes were received for no than yes.)

Features

This protocol works as long as not all of the k authorities are corrupt—if they were, then they could collaborate to reconstruct P(x) for each voter and then alter the votes.

The protocol requires t+1 authorities to be completed, therefore in case there are N>t+1 authorities, N-t-1 authorities can be corrupted, which gives the protocol a certain degree of robustness.

The protocol manages the IDs of the voters (the IDs were submitted with the ballots) and therefore can verify that only legitimate voters have voted.

Under the assumptions on t:

  1. A ballot can not be backtracked to the ID so the privacy of the voters is preserved.
  2. A voter can not prove how he voted.
  3. It is impossible to verify a vote.

The protocol implicitly prevents corruption of ballots. This is because the authorities has no incentive to change the ballot since each authority has only a share of the ballot and has no knowledge how changing the ballot will affect the outcome.

Vulnerabilities

References

  1. ^ Schoenmakers, Berry (1999). Advances in Cryptology 1666: 148–164. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.102.9375&rep=rep1&type=pdf. 

See also